package likou;


import java.util.*;
import java.util.concurrent.locks.AbstractQueuedSynchronizer;

/**
 * @description:
 * @title: LeetCodeDemo
 * @author: zp
 * @date: 2021/8/15 21:24
 */

public class LeetCodeDemo{
    public static void main(String[] args) {
        LRUCache lRUCache = new LRUCache(2);
        lRUCache.put(1, 1); // 缓存是 {1=1}
        lRUCache.put(2, 2); // 缓存是 {1=1, 2=2}
        lRUCache.get(1);    // 返回 1
        lRUCache.put(3, 3); // 该操作会使得关键字 2 作废，缓存是 {1=1, 3=3}
        lRUCache.get(2);    // 返回 -1 (未找到)
        lRUCache.put(4, 4); // 该操作会使得关键字 1 作废，缓存是 {4=4, 3=3}
        lRUCache.get(1);    // 返回 -1 (未找到)
        lRUCache.get(3);    // 返回 3
        lRUCache.get(4);    // 返回 4


    }
    /**
     * @description: 两数相加
     * @author: zp
     * @date: 2021/8/17 20:59
     * @param: l1
     * @param: l2
     * @return: likou.ListNode
     */
    public static ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode pre = new ListNode(0);
        ListNode cur = pre;
        int carry = 0;
        while(l1 != null || l2 != null) {
            int x = l1 == null ? 0 : l1.val;
            int y = l2 == null ? 0 : l2.val;
            int sum = x + y + carry;

            carry = sum / 10;
            sum = sum % 10;
            cur.next = new ListNode(sum);

            cur = cur.next;
            if(l1 != null){
                l1 = l1.next;
            }

            if(l2 != null){
                l2 = l2.next;
            }

        }
        //逢10 进一位
        if(carry == 1) {
            cur.next = new ListNode(carry);
        }
        return pre.next;
    }
    /**
     * @description:
     * @author: zp
     * @date: 2021/8/17 21:00
     * @param: nums
     * @param: target
     * @return: int[]
     * 两数之和
     */
    public static int[] twoSum1(int[] nums, int target) {
        int[] towSumIndex=new int[2];
        for (int i = 0; i <nums.length ; i++) {
            for(int j = i+1; j <nums.length ; j++){
                if(nums[i]+nums[j]==target){
                    towSumIndex[0]=i;
                    towSumIndex[1]=j;
                }
            }
        }
        return towSumIndex;
    }

    public static int[] twoSum2(int[] nums, int target) {
        int n = nums.length;
        //声明一个HashMap，key和value的类型都是int，变量名叫map。key和value分别记录数值和下标
        HashMap<Integer, Integer> map = new HashMap<>();
        for(int i = 0; i < n; i++){
            //如果存在nums[j] + nums[i] == target，那么nums[j] = target - nums[i]
            int diff = target - nums[i];
            //如果存在diff，则返回diff和nums[i]的下标
            //HashMap的containsKey方法判断该HashMap中是否存在这个key
            if(map.containsKey(diff)){
                //返回的时候直接创建一个数组，创建数组时可以直接初始化，就不需要填大小了，比如说new int[]{1, 2, 3};
                //此时创建一个大小为2的数组，第一个元素为map.get(diff)也就是map中对应diff的value，第二个元素就是i，也就是2个数的下标
                return new int[]{map.get(diff), i};
            }else {  //否则，将nums[i]存入map中
                map.put(nums[i], i);
            }
        }
        return new int[0];
    }


    public static int lengthOfLongestSubstring(String s) {
            // 哈希集合，记录每个字符是否出现过
            Set<Character> occ = new HashSet<Character>();
            int n = s.length();
            // 右指针，初始值为 -1，相当于我们在字符串的左边界的左侧，还没有开始移动
            int rk = -1, ans = 0;
            for (int i = 0; i < n; ++i) {
                if (i != 0) {
                    // 左指针向右移动一格，移除一个字符
                    occ.remove(s.charAt(i - 1));
                }
                while (rk + 1 < n && !occ.contains(s.charAt(rk + 1))) {
                    // 不断地移动右指针
                    occ.add(s.charAt(rk + 1));
                    ++rk;
                }
                // 第 i 到 rk 个字符是一个极长的无重复字符子串
                ans = Math.max(ans, rk - i + 1);
            }
            return ans;
        }
    /**
     * @description: 求俩个从大到小的数组中 求出中位数
     * @author: zp
     * @date: 2021/8/21 14:29
     * @param: nums1
     * @param: nums2
     * @return: double
     */
    public static double findMedianSortedArrays1(int[] nums1, int[] nums2) {
        int count = nums1.length+nums2.length;
        int[] nums3 = new int[count];
        int temp;
        int aveIndex;
        if(count == 0){
            return 0;
        }
        for (int i = 0; i <nums1.length ; i++) {
            nums3[i]=nums1[i];
        }
        for (int i = 0; i <nums2.length ; i++) {
            nums3[i+nums1.length]=nums2[i];
        }
        for (int i = 0; i <nums3.length ; i++) {
            for (int j = 0; j <nums3.length ; j++) {
                if(nums3[i]>nums3[j]){
                    temp=nums3[j];
                    nums3[j]=nums3[i];
                    nums3[i]=temp;
                }
            }
        }

        aveIndex=count/2;
        if(count%2>0){
            return (double) nums3[aveIndex];
        }

        return (double) (nums3[aveIndex-1]+nums3[aveIndex])/2;
    }

    public static double findMedianSortedArrays2(int[] A, int[] B) {
        int m = A.length;
        int n = B.length;
        int len = m + n;
        int left = -1, right = -1;
        int aStart = 0, bStart = 0;
        for (int i = 0; i <= len / 2; i++) {
            left = right;
            if (aStart < m && (bStart >= n || A[aStart] < B[bStart])) {
                right = A[aStart++];
            } else {
                right = B[bStart++];
            }
        }
        if ((len & 1) == 0) {
            return (left + right) / 2.0;
        } else {
            return right;
        }
    }
    /**
     * @description:求最长回文子字符串
     * @author: zp
     * @date: 2021/8/21 14:30
     * @param: s
     * @return: boolean
     */
    public static boolean isPalindromic(String s) {
        int len = s.length();
        for (int i = 0; i < len / 2; i++) {
            if (s.charAt(i) != s.charAt(len - i - 1)) {
                return false;
            }
        }
        return true;
    }
    /**
     * @description:寻找回文正整数字符串
     * @author: zp
     * @date: 2021/8/21 20:48
     * @param: x
     * @return: boolean
     */
    public static boolean isPalindrome(int x) {
        if(x<0){
            return false;
        }
        String s= String.valueOf(x);
        int len = s.length();
        for (int i = 0; i < len / 2; i++) {
            if (s.charAt(i) != s.charAt(len - i - 1)) {
                return false;
            }
        }
        return true;
    }

    /**
     * @description:
     * @author: zp
     * @date: 2021/8/19 20:40
     * @param: s
     * @return: java.lang.String
     * 暴力破解 求最长回文子字符串
     */
    public static String longestPalindrome(String s) {
        String ans = "";
        int max = 0;
        int len = s.length();
        for (int i = 0; i < len; i++) {
            for (int j = i + 1; j <= len; j++) {
                String test = s.substring(i, j);
                if (isPalindromic(test) && test.length() > max) {
                    ans = s.substring(i, j);
                    max = Math.max(max, ans.length());
                }
            }
        }
        return ans;
    }
    /**
     * @description:翻转数字 如果头位为0 省略 范围2-31次方到-2-31次方
     * @author: zp
     * @date: 2021/8/21 15:06
     * @param: x
     * @return: int
     */
    public static int reverse(int x) {
        if(String.valueOf(x).trim().length()<2){
            return x;
        }
        int n=x;
        while(n % 10 == 0){
            n = n / 10;
        }
        StringBuffer s= new StringBuffer(String.valueOf(Math.abs(n)));
        String key=s.reverse().toString();
        double value = Double.parseDouble(key);
        if(value > Integer.MAX_VALUE){
            return 0;
        }
        if(x<0){
            return (int)(value*-1);
        }
        return (int)value;
    }
    /**
     * @description:
     * @author: zp
     * @date: 2021/8/21 15:07
     * @param: s
     * @return: int
     * 读入字符串并丢弃无用的前导空格
     * 检查下一个字符（假设还未到字符末尾）为正还是负号，读取该字符（如果有）。 确定最终结果是负数还是正数。 如果两者都不存在，则假定结果为正。
     * 读入下一个字符，直到到达下一个非数字字符或到达输入的结尾。字符串的其余部分将被忽略。
     * 将前面步骤读入的这些数字转换为整数（即，"123" -> 123， "0032" -> 32）。如果没有读入数字，则整数为 0 。必要时更改符号（从步骤 2 开始）。
     * 如果整数数超过 32 位有符号整数范围 [−231,  231 − 1] ，需要截断这个整数，使其保持在这个范围内。具体来说，小于 −231 的整数应该被固定为 −231 ，大于 231 − 1 的整数应该被固定为 231 − 1 。
     * 返回整数作为最终结果。
     */
    public static int myAtoi(String s) {
        if(s.length()>200 || s.trim().length()==0){
            return 0;
        }
        //清除前后置空格
        s=s.trim();
        char[] cs=s.toCharArray();
        int x=0;
        StringBuffer stringBuffer = new StringBuffer();
        if(cs[0]=='-'){
            for (int i = 1; i <cs.length ; i++) {
                if(!(cs[i]>=48 && cs[i]<=58) || cs[i]==' '){
                    break;
                }
                if(!(cs[i]==' ')){
                    if(x==0){
                        if(cs[i]!=48){
                            x++;
                            stringBuffer.append(cs[i]);
                        }

                    }else {
                        stringBuffer.append(cs[i]);
                    }

                }

            }
            if(stringBuffer.toString().trim().length()>0){
                double value = Double.parseDouble(stringBuffer.toString());
                if(value*-1<=Integer.MIN_VALUE){
                    return Integer.MIN_VALUE;
                }
                return (int)value*-1;
            }
            return 0;

        }else if(cs[0]=='+'){
            for (int i = 1; i <cs.length ; i++) {
                if(!(cs[i]>=48 && cs[i]<=58) || cs[i]==' '){
                    break;
                }
                if(!(cs[i]==' ')){
                    if(x==0){
                        if(cs[i]!=48){
                            x++;
                            stringBuffer.append(cs[i]);
                        }

                    }else {
                        stringBuffer.append(cs[i]);
                    }

                }

            }
            if(stringBuffer.toString().trim().length()>0) {
                double value = Double.parseDouble(stringBuffer.toString());
                if (value > Integer.MAX_VALUE) {
                    return Integer.MAX_VALUE;
                }
                return (int) value;
            }
            return 0;
        }else if(cs[0]>=48 && cs[0]<=58){
            for (int i = 0; i <cs.length ; i++) {
                if(!(cs[i]>=48 && cs[i]<=58) || cs[i]==' '){
                    break;
                }
                if(!(cs[i]==' ')){
                    if(x==0){
                        if(cs[i]!=48){
                            x++;
                            stringBuffer.append(cs[i]);
                        }

                    }else {
                        stringBuffer.append(cs[i]);
                    }

                }

            }
            if(stringBuffer.toString().trim().length()>0) {
                double value = Double.parseDouble(stringBuffer.toString());
                if (value > Integer.MAX_VALUE) {
                    return Integer.MAX_VALUE;
                }
                return (int) value;
            }
            return 0;
        }
        return 0;
    }
    /**
     * @description: 正则表达式匹配
     * @author: zp
     * @date: 2021/8/22 14:49
     * @param: s
     * @param: p
     * @return: boolean
     * 给你一个字符串 s 和一个字符规律 p，请你来实现一个支持 '.' 和 '*' 的正则表达式匹配。
     *
     * '.' 匹配任意单个字符
     * '*' 匹配零个或多个前面的那一个元素
     * 所谓匹配，是要涵盖 整个 字符串 s的，而不是部分字符串。
     */
    public static boolean isMatch(String s, String p) {
        int m = s.length();
        int n = p.length();

        boolean[][] f = new boolean[m + 1][n + 1];
        f[0][0] = true;
        for (int i = 0; i <= m; ++i) {
            for (int j = 1; j <= n; ++j) {
                if (p.charAt(j - 1) == '*') {
                    f[i][j] = f[i][j - 2];
                    if (matches(s, p, i, j - 1)) {
                        f[i][j] = f[i][j] || f[i - 1][j];
                    }
                } else {
                    if (matches(s, p, i, j)) {
                        f[i][j] = f[i - 1][j - 1];
                    }
                }
            }
        }
        return f[m][n];
    }

    public static boolean matches(String s, String p, int i, int j) {
        if (i == 0) {
            return false;
        }
        if (p.charAt(j - 1) == '.') {
            return true;
        }
        return s.charAt(i - 1) == p.charAt(j - 1);
    }
    /**
     * @description: 盛最多水的容器
     * @author: zp
     * @date: 2021/8/22 15:01
     * @param: height
     * @return: int
     */
    public static int maxArea(int[] height) {
            int l = 0, r = height.length - 1;
            int ans = 0;
            while (l < r) {
                int area = Math.min(height[l], height[r]) * (r - l);
                ans = Math.max(ans, area);
                if (height[l] <= height[r]) {
                    ++l;
                }
                else {
                    --r;
                }
            }
            return ans;
        }
    /**
     * @description:罗马数字转整数
     * @author: zp
     * @date: 2021/8/23 21:06
     * @param: s
     * @return: int
     */
    public static int romanToInt(String s) {
        Map<Character, Integer> map = new HashMap<Character, Integer>() {{
            put('I', 1);
            put('V', 5);
            put('X', 10);
            put('L', 50);
            put('C', 100);
            put('D', 500);
            put('M', 1000);
        }};
        int sum = 0;
        char[] cs = s.toCharArray();
        for (int i = 0; i <cs.length ; i++) {
            int value = map.get(cs[i]);
            //从左到右取数据 当当前一个值的对应数字 小于下一个字符 那这个字符就是4或者9 或者是其10的整数倍 然后只要在原有的基础上减去就可以
            if(i<cs.length-1 && value<map.get(cs[i+1])){
                sum-=value;
            }else {
                sum+=value;
            }
        }
        return sum;
    }
    /**
     * @description: 编写一个函数来查找字符串数组中的最长公共前缀
     * @author: zp
     * @date: 2021/8/23 21:57
     * @param: strs
     * @return: java.lang.String
     */
    public static String longestCommonPrefix(String[] strs) {
        if(strs.length>=1) {
            String minStr = strs[0];
            int count = 0;
            for (int i = 0; i < strs.length; i++) {
                if (strs[i].length() <= minStr.length()) {
                    minStr = strs[i];
                    count = i;
                }
            }
            List<Boolean> flags = new ArrayList<>();
            boolean put = true;
            for (int i = minStr.length(); i > 0; i--) {
                boolean flag;
                for (int j = 0; j < strs.length; j++) {
                    if (j == count) {
                        continue;
                    }
                    flag = minStr.substring(0, i).equalsIgnoreCase(strs[j].substring(0, i));
                    flags.add(flag);
                }
                for (int j = 0; j < flags.size(); j++) {
                    if (!flags.get(j)) {
                        put = flags.get(j);
                        break;
                    }
                }
                if (put) {
                    return minStr.substring(0, i);
                }
                put = true;
                flags.clear();
            }
        }
        return "";
    }
    /**
     * @description:三数之和
     * @author: zp
     * @date: 2021/8/24 20:53
     * @param: nums
     * @return: java.util.List<java.util.List<java.lang.Integer>>
     *     给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有和为 0 且不重复的三元组。
     *
     *      注意：答案中不可以包含重复的三元组。
     */
    public static List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> ans = new ArrayList();
        int len = nums.length;
        if(nums == null || len < 3) {
            return ans;
        }
        Arrays.sort(nums); // 排序
        for (int i = 0; i < len ; i++) {
            if(nums[i] > 0) {
                break;
            } // 如果当前数字大于0，则三数之和一定大于0，所以结束循环
            if(i > 0 && nums[i] == nums[i-1]) {
                continue;
            } // 去重
            int L = i+1;
            int R = len-1;
            while(L < R){
                int sum = nums[i] + nums[L] + nums[R];
                if(sum == 0){
                    ans.add(Arrays.asList(nums[i],nums[L],nums[R]));
                    while (L<R && nums[L] == nums[L+1]) {
                        L++; // 去重
                    }
                    while (L<R && nums[R] == nums[R-1]) {
                        R--; // 去重
                    }
                    L++;
                    R--;
                }
                else if (sum < 0) {
                    L++;
                }
                else if (sum > 0) {
                    R--;
                }
            }
        }
        return ans;
    }

    public static int threeSumClosest(int[] nums, int target) {
            Arrays.sort(nums);
            int n = nums.length;
            int best = 10000000;

            // 枚举 a
            for (int i = 0; i < n; ++i) {
                // 保证和上一次枚举的元素不相等
                if (i > 0 && nums[i] == nums[i - 1]) {
                    continue;
                }
                // 使用双指针枚举 b 和 c
                int j = i + 1, k = n - 1;
                while (j < k) {
                    int sum = nums[i] + nums[j] + nums[k];
                    // 如果和为 target 直接返回答案
                    if (sum == target) {
                        return target;
                    }
                    // 根据差值的绝对值来更新答案
                    if (Math.abs(sum - target) < Math.abs(best - target)) {
                        best = sum;
                    }
                    if (sum > target) {
                        // 如果和大于 target，移动 c 对应的指针
                        int k0 = k - 1;
                        // 移动到下一个不相等的元素
                        while (j < k0 && nums[k0] == nums[k]) {
                            --k0;
                        }
                        k = k0;
                    } else {
                        // 如果和小于 target，移动 b 对应的指针
                        int j0 = j + 1;
                        // 移动到下一个不相等的元素
                        while (j0 < k && nums[j0] == nums[j]) {
                            ++j0;
                        }
                        j = j0;
                    }
                }
            }
            return best;
        }
    /**
     * @description:
     * @author: zp
     * @date: 2021/8/28 14:25
     * @param: digits
     * @return: java.util.List<java.lang.String>
     *     返回九键输入法的对应字母组合 2-9的范围
     */
    public static List<String>  letterCombinations(String digits) {
        List<String> combinations = new ArrayList<String>();
        if (digits.length() == 0) {
            return combinations;
        }
        Map<Character, String> phoneMap = new HashMap<Character, String>() {{
            put('2', "abc");
            put('3', "def");
            put('4', "ghi");
            put('5', "jkl");
            put('6', "mno");
            put('7', "pqrs");
            put('8', "tuv");
            put('9', "wxyz");
        }};
        backtrack(combinations, phoneMap, digits, 0, new StringBuffer());
        return combinations;
    }

    public static void backtrack(List<String> combinations, Map<Character, String> phoneMap, String digits, int index, StringBuffer combination) {
        if (index == digits.length()) {
            combinations.add(combination.toString());
        } else {
            char digit = digits.charAt(index);
            String letters = phoneMap.get(digit);
            int lettersCount = letters.length();
            for (int i = 0; i < lettersCount; i++) {
                combination.append(letters.charAt(i));
                backtrack(combinations, phoneMap, digits, index + 1, combination);
                combination.deleteCharAt(index);
            }
        }
    }
    /**
     * @description:
     * @author: zp
     * @date: 2021/8/28 17:15
     * @param: s
     * @return: boolean
     * 判断括号是否有对应的括号
     */
    public static boolean isValid(String s) {
        int n = s.length();
        //括号一定是成对出现 如果出现单数 一定不符合要求
        if (n % 2 == 1) {
            return false;
        }
        //把相反的括号对应放入map
        Map<Character, Character> pairs = new HashMap<Character, Character>() {{
            put(')', '(');
            put(']', '[');
            put('}', '{');
        }};
        //创建一个队列
        Deque<Character> stack = new LinkedList<>();
        for (int i = 0; i < n; i++) {
            char ch = s.charAt(i);
            //判断输入字符是否在给定字符中
            if (pairs.containsKey(ch)) {
                //判断队列是否有元素 取出来的元素是否对应
                if (stack.isEmpty() || !stack.peek() .equals(pairs.get(ch))) {
                    return false;
                }
                //如果有对应的 把元素消费
                stack.pop();
            } else {
                //如果没有对应的括号消费元素 把取出来的字符串放入队列中
                stack.push(ch);
            }
        }
        //最后当循环走完 查看队列中是否还有元素 如果没有就全部完成匹配返回true  如果有就是输入的字符串不符合 返回false
        return stack.isEmpty();
    }
    /**
     * @description: 二分查找
     * @author: zp
     * @date: 2021/9/19 13:54
     * @param: nums
     * @param: target
     * @return: int
     */
    public static int search(int[] nums, int target) {
        int minNum=nums.length/2;
        if(target==nums[minNum]){
            return minNum;
        }else if(target<nums[minNum]){
            for (int i = 0; i <minNum ; i++) {
                if(target==nums[i]){
                    return i;
                }
            }
        }else {
            for (int i = minNum+1; i <nums.length ; i++) {
                if(target==nums[i]){
                    return i;
                }
            }
        }
        return -1;
    }
}
